Compilers are generally used to transform one representation of a computer program into another representation. Typically, but not exclusively, compilers are used to transform a human-readable form of a program, such as source code, into a machine-readable form, such as object code.
One type of compiler is an optimizing compiler, which optimizes object code in order to enhance its performance. An optimizing compiler can attempt to enhance performance by reducing the overhead associated with two common, programming techniques known as procedural programming and object-oriented programming.
In procedural programming, a program is broken into many small procedures, each including a sequence of statements (and in some cases, data), and each of which is responsible for particular, well-defined activities. The procedures are invoked, or called, when particular actions are needed. Typically, procedures can invoke each other, as part of operation of the program. In such a situation, the procedure that is invoked is typically referred to as the “child” procedure, and the procedure that invokes the child procedure is referred to as the “parent” procedure. When the parent procedure invokes the child procedure, control is transferred from the parent to the child, so that the child is now executing instead of the parent.
While procedural programming can simplify programming effort and reduce complexity, one of the unfortunate results of a highly-procedural computer program is that the program, when operating, frequently transfers control between the various procedures (i.e., it executes “procedure calls”). This creates overhead that degrades performance of the program because each transfer of control between procedures requires multiple computer operations, both to transfer flow control to a procedure and to return flow control from the procedure.
A similar, unfortunate result occurs in object-oriented programming. In object-oriented programming, data and a set of procedures (called “methods”) are encapsulated together, and only the procedures encapsulated with data are permitted to modify that data. This style of programming naturally causes procedure calls to proliferate and procedure sizes to shrink, typically to a greater extent than in procedural programming.
To address this problem of high procedure-call overhead, modern compilers optimize programs so as to avoid procedure calls. One optimization approach is called inlining. Although the details can be somewhat complex, the idea is simple: the compiler replaces a call to a procedure by a duplicate of the body of the called procedure. The advantages of inlining are (1) removal of the call overhead required by the procedure-calling conventions; and (2) increased optimization opportunities that can arise when the compiler can see the called-procedure's instructions in context.
Of course, there are disadvantages to inlining as well. One problem that can arise is that of excessive register pressure. Register pressure is a measure of the number of values that must be remembered by the compiled program at a given point during execution. For example, in a complex mathematical expression, it may be necessary to keep a number of different values in registers at the same time, as intermediate results of the expression. If the number of registers required at any point (the pressure) exceeds the number of available physical registers in the processor, some of the values must be maintained in slower main memory instead of the registers. Thus, we say that some of the values have been “spilled” to main memory.
It is, therefore, undesirable to inline a child procedure into a parent procedure if to do so would increase register pressure to the point that register spill occurs (or at least to the point that the cost of any spill that does occur exceeds the benefit from inlining). Prior inliners have not adequately addressed this problem. Some inliners do nothing at all to address the problem, in which case performance is reduced when a register spill occurs. Other inliners have avoided unnecessary register pressure by indirect means such as not allowing the parent procedure to grow beyond a threshold size due to inlining. But, procedure size is not a reliable measure of register pressure; very large procedures do not necessarily suffer from register spill. Thus, these inliners fail to gain the performance benefits of inlining in many cases where it would improve performance greatly.
Thus, there is a need for a compiler that will make direct use of register-pressure information in making inlining decisions.